翻訳と辞書 Words near each other ・ Cycloteuthidae ・ Cycloteuthis ・ Cycloteuthis sirventi ・ Cyclothea ・ Cyclotheca ・ Cyclothems ・ Cyclothiazide ・ Cyclothiazomycin ・ Cyclothone ・ Cyclothorax ・ Cyclothymia ・ Cyclothyris ・ Cyclotide ・ Cyclotol ・ Cyclotomic character ・ Cyclotomic fast Fourier transform ・ Cyclotomic field ・ Cyclotomic identity ・ Cyclotomic polynomial ・ Cyclotomic unit ・ Cyclotorna ・ Cyclotorna diplocentra ・ Cyclotorna egena ・ Cyclotorna ementita ・ Cyclotorna experta ・ Cyclotorna monocentra ・ Cyclotosaurus ・ Cyclotrachelus ・ Cyclotrichium ・ Cyclotridecane Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Cyclotomic fast Fourier transform ： ウィキペディア英語版 Cyclotomic fast Fourier transform The cyclotomic fast Fourier transform is a type of fast Fourier transform algorithm over finite fields.〔S.V. Fedorenko and P.V. Trifonov, 〕 This algorithm first decomposes a DFT into several circular convolutions, and then derives the DFT results from the circular convolution results. When applied to a DFT over $GF(2^m)$, this algorithm has a very low multiplicative complexity. In practice, since there usually exist efficient algorithms for circular convolutions with specific lengths, this algorithm is very efficient. == Background == The discrete Fourier transform over finite fields finds widespread application in the decoding of error-correcting codes such as BCH codes and Reed–Solomon codes. Generalized from the complex field, a discrete Fourier transform of a sequence $\backslash \_^$ over a finite field GF(''p''''m'') is defined as :$F\_j=\backslash sum\_^f\_i\backslash alpha^,\; 0\backslash le\; j\backslash le\; N-1,$ where $\backslash alpha$ is the ''N''-th primitive root of 1 in GF(''p''''m''). If we define the polynomial representation of $\backslash \_^$ as :$f(x)\; =\; f\_0+f\_1x+f\_2x^2+\backslash cdots+f\_x^=\backslash sum\_^f\_ix^i,$ it is easy to see that $F\_j$ is simply $f(\backslash alpha^j)$. That is, the discrete Fourier transform of a sequence converts it to a polynomial evaluation problem. Written in matrix format, :$\backslash mathbf=\backslash left(\backslash vdots\; \backslash \backslash \; F\_\backslash end\backslash right)=$ \left(&\cdots & \alpha^0\\ \alpha^0 & \alpha^1 &\cdots &\alpha^\\ \vdots &\vdots & \ddots & \vdots \\ \alpha^ & \alpha^ &\cdots & \alpha^ \end\right ) \left()=\mathcal\mathbf. Direct evaluation of DFT has an $O(N^2)$ complexity. Fast Fourier transforms are just efficient algorithms evaluating the above matrix-vector product. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cyclotomic fast Fourier transform」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.